package main

import (
	"fmt"
	"os"
)

/**
 * 广度优先 走迷宫
 */
func main() {
	maze := readMaze("src/maze/maze.in")
	testReadMaze(maze)
	steps := walk(maze, point{0, 0}, point{len(maze) - 1, len(maze[0]) - 1})

	printMazeSolution(steps)
}

// 读取迷宫文件
func readMaze(filename string) [][]int {
	// 1. 打开文件
	file, err := os.Open(filename)
	if err != nil {
		panic(err)
	}

	var row, col int
	// 2.读取第一行
	fmt.Fscanf(file, "%d %d\n", &row, &col)

	maze := make([][]int, row) // 有多少个silce int ,即多少行 []int
	for i := range maze {
		maze[i] = make([]int, col) // 每一行有几列
		fmt.Fscanf(file, "%d %d %d %d %d\n", &maze[i][0], &maze[i][1], &maze[i][2], &maze[i][3], &maze[i][4])
		/*for j := range maze[i] {
			fmt.Fscanf(file, "%d", &maze[i][j])
		}*/
	}
	return maze
}

func printMazeSolution(steps [][]int) {
	// 打印存储所有步数的二维数组
	for _, row := range steps {
		for _, val := range row {
			fmt.Printf("%3d", val)
		}
		fmt.Println()
	}
}

// 点的结构体
type point struct {
	i, j int
}

// 定义 上左下右
var dirs = [4]point{
	{-1, 0}, {0, -1}, {1, 0}, {0, 1}}

// 点和点相加(没有操作符重载)
func (p point) add(r point) point {
	return point{p.i + r.i, p.j + r.j}
}

/**
第一个返回值
第二个返回是否有效
*/
func (p point) at(grid [][]int) (int, bool) {
	// 判断是否越界
	if p.i < 0 || p.i >= len(grid) {
		return 0, false
	}

	if p.j < 0 || p.j >= len(grid[p.i]) {
		return 0, false
	}

	return grid[p.i][p.j], true
}

// 走迷宫
func walk(maze [][]int, start, end point) [][]int {
	// 记录走到的每一个格子的步数
	steps := make([][]int, len(maze))
	for i := range steps {
		steps[i] = make([]int, len(maze[i]))
	}

	// 起点加进队列
	Q := []point{start}

	// 队列不为空
	for len(Q) > 0 {
		cur := Q[0] // 当前节点
		Q = Q[1:]   // 出队

		// 发现终点 退出
		if cur == end {
			break
		}

		for _, dir := range dirs {
			// 新发现节点 = 当前节点加上方向
			next := cur.add(dir)

			// maze at next is 0
			// and steps at next is 0(曾将探索过)
			// and next != start 才能探索
			val, ok := next.at(maze)
			if !ok || val == 1 { // 越界 或者是墙
				continue
			}

			val, ok = next.at(steps)
			if !ok || val != 0 { // 越界或者曾经探索过
				continue
			}

			if next == start { // 是终点
				continue
			}

			// 探索 1.将step+1 2.将可以探索的点加入队列
			curSteps, _ := cur.at(steps)
			steps[next.i][next.j] = curSteps + 1

			Q = append(Q, next)
		}
	}

	return steps
}

// 测试读取迷宫是否正确
func testReadMaze(maze [][]int) {
	for _, row := range maze {
		for _, val := range row {
			fmt.Printf("%d ", val)
		}
		fmt.Println()
	}
}
